\subsubsection{std::list}
\myindex{\Cpp!STL!std::list}
\label{std_list}
\index{Двусвязный список}

Хорошо известный всем двусвязный список: каждый элемент имеет два указателя, на следующий и на предыдущий
элементы.

Это означает, что расход памяти увеличивается на 2 \glslink{word}{слова} на каждый элемент (8 байт в 32-битной среде или
16 байт в 64-битной).

STL в \Cpp просто добавляет указатели \q{next} и \q{previous} к той вашей структуре, которую вы желаете объединить в список.

Попробуем разобраться с примером в котором простая структура из двух переменных, мы объединим её в список.

Хотя и стандарт \Cpp не указывает, как он должен быть реализован, реализации
MSVC и GCC простые и похожи друг на друга, так что этот исходный код для обоих:

\lstinputlisting[style=customc]{\CURPATH/STL/list/2_RU.cpp}

\myparagraph{GCC}

Начнем с GCC.

При запуске увидим длинный вывод, будем разбирать его по частям.

\begin{lstlisting}
* empty list:
ptr=0x0028fe90 _Next=0x0028fe90 _Prev=0x0028fe90 x=3 y=0
\end{lstlisting}

Видим пустой список.
Не смотря на то что он пуст, имеется один элемент с мусором (\ac{AKA} узел-пустышка (\IT{dummy node})) 
в переменных $x$ и $y$.

Оба указателя \q{next} и \q{prev} указывают на себя:

\input{\CURPATH/STL/list/empty_list}

Это тот момент, когда итераторы .begin и .end равны друг другу.

Вставим 3 элемента и список в памяти будет представлен так:

\begin{lstlisting}
* 3-elements list:
ptr=0x000349a0 _Next=0x00034988 _Prev=0x0028fe90 x=3 y=4
ptr=0x00034988 _Next=0x00034b40 _Prev=0x000349a0 x=1 y=2
ptr=0x00034b40 _Next=0x0028fe90 _Prev=0x00034988 x=5 y=6
ptr=0x0028fe90 _Next=0x000349a0 _Prev=0x00034b40 x=5 y=6
\end{lstlisting}

Последний элемент всё еще на 0x0028fe90, 
он не будет передвинут куда-либо до самого уничтожения списка.

Он все еще содержит случайный мусор в полях $x$ и $y$ (5 и 6). 
Случайно совпало так, что эти значения точно такие же, как и в последнем элементе, но это не значит,
что они имеют какое-то значение.

Вот как эти 3 элемента хранятся в памяти:

\input{\CURPATH/STL/list/GCC_internals}

Переменная $l$ всегда указывает на первый элемент.

Итераторы .begin() и .end() это не переменные, а функции,
возвращающие указатели на соответствующие узлы.

Иметь элемент-пустышку (\IT{dummy node} или \IT{sentinel node}) это очень популярная практика в реализации двусвязных списков.%

Без него, многие операции были бы сложнее, и, следовательно, медленнее.

Итератор на самом деле это просто указатель на элемент.
list.begin() и list.end() просто возвращают указатели.

\begin{lstlisting}
node at .begin:
ptr=0x000349a0 _Next=0x00034988 _Prev=0x0028fe90 x=3 y=4
node at .end:
ptr=0x0028fe90 _Next=0x000349a0 _Prev=0x00034b40 x=5 y=6
\end{lstlisting}

Тот факт, что что последний элемент имеет указатель на первый 
и первый имеет указатель на последний, напоминает нам циркулярный список.

Это очень помогает: если иметь указатель только на первый элемент, т.е.
тот что в переменной $l$, очень легко получить указатель на последний элемент, без необходимости
обходить все элементы списка.
Вставка элемента в конец списка также быстра благодаря этой особенности.

\TT{operator--} и \TT{operator++} просто выставляют текущее значение итератора на \TT{current\_node->prev} или \TT{current\_node->next}.

Обратные итераторы (.rbegin, .rend) работают точно так же, только наоборот.

\TT{operator*} на итераторе просто возвращает указатель на место в структуре, где начинается пользовательская
структура, т.е. указатель на самый первый элемент структуры ($x$).

Вставка в список и удаление очень просты: просто выделите новый элемент (или освободите) и исправьте
все указатели так, чтобы они были верны.

Вот почему итератор может стать недействительным после удаления элемента:
он может всё еще указывать на уже освобожденный элемент.

Это также называется \IT{dangling pointer}.
И конечно же, информация из освобожденного элемента, на который указывает итератор, 
не может использоваться более.

В реализации GCC (по крайней мере 4.8.1) не сохраняется текущая длина списка: это выливается в медленный
метод .size(): он должен пройти по всему списку считая элементы, просто потому что нет
другого способа получить эту информацию.
Это означает, что эта операция $O(n)$, т.е. она работает тем медленнее, чем больше элементов в списке.

\lstinputlisting[caption=\Optimizing GCC 4.8.1 -fno-inline-small-functions,style=customasmx86]{\CURPATH/STL/list/GCC_RU.asm}

\lstinputlisting[caption=Весь вывод]{\CURPATH/STL/list/GCC.txt}

\myparagraph{MSVC}
\label{MSVC_std_list}

Реализация MSVC (2012) точно такая же, только еще и сохраняет текущий размер списка.
Это означает, что метод .size() очень быстр ($O(1)$): просто прочитать одно значение из памяти.
С другой стороны, переменная хранящая размер должна корректироваться при каждой вставке/удалении.

Реализация MSVC также немного отлична в смысле расстановки элементов:

\input{\CURPATH/STL/list/MSVC_internals}

У GCC его элемент-пустышка в самом конце списка, а у MSVC в самом начале.

\lstinputlisting[caption=\Optimizing MSVC 2012 /Fa2.asm /GS- /Ob1,style=customasmx86]{\CURPATH/STL/list/MSVC_RU.asm}

В отличие от GCC, код MSVC выделяет элемент-пустышку в самом начале функции при помощи
функции \q{Buynode}, она также используется и во время выделения остальных элементов
(код GCC выделяет самый первый элемент в локальном стеке).

\lstinputlisting[caption=Весь вывод]{\CURPATH/STL/list/MSVC.txt}

\myparagraph{C++11 std::forward\_list}
\myindex{\Cpp!STL!std::forward\_list}

Это то же самое что и std::list, но только односвязный список, т.е. имеющий только поле \q{next} в каждом
элементе.
Таким образом расход памяти меньше, но возможности идти по списку назад здесь нет.

